/**
 * 
 */
package array.passed;

/**
 * @author xyyi
 *
 */
public class SearchInRotatedSortedArrayII {

	/**
	Follow up for "Search in Rotated Sorted Array":
	What if duplicates are allowed?

	Would this affect the run-time complexity? How and why?

	Write a function to determine if a given target is in the array.
	 */
	public boolean search(int[] A, int target) {
		if (A == null || A.length == 0)
			return false;

		int left = 0, right = A.length - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (A[mid] == target)
				return true;
			if (A[left] < A[mid]) {
				if (target >= A[left] && target < A[mid])
					right = mid - 1;
				else
					left = mid + 1;
			} else if (A[left] > A[mid]) {
				if (target > A[mid] && target <= A[right])
					left = mid + 1;
				else
					right = mid - 1;
			} else
				left++;
		}

		return false;
	}

	/**
	 * 
	 */
	public SearchInRotatedSortedArrayII() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
